#include<iostream>
using namespace std;
class CPrefixSorting{
public:
    CPrefixSorting(){
            m_nCakeCnt=0;
            m_nMaxSwap=0;
    }

    ~CPrefixSorting(){
        if(m_CakeArray!=NULL){
            delete m_CakeArray;
        }
        if(m_SwapArray!=NULL){
            delete m_SwapArray;
        }
    }
    //计算烙饼翻转信息
    void Run(int* pCakeArray,int nCakeCnt){ //存储索引数组和烙饼个数
        Init(pCakeArray,nCakeCnt);
        m_nsearch=0;
        Search(0);
    }
    //输出烙饼翻转次数
    /*
    void Output(){
        for(int i=0;i<m_nMaxSwap;i++){
            printf("%d",m_arrSwap[i]);
        }

    }
    */
private:
    //初始化数组信息
    void Init(int* pCakeArray,int nCakeCnt){
        assert(pCakeArray!=NULL);
        assert(nCakeCnt>0);
        m_nCakeCnt=nCakeCnt;
        m_CakeArray=new int[m_nCakeCnt];
        assert(m_CakeArray!=NULL);
        for(int i=0;i<m_nCakeCnt;i++){
            m_CakeArray[i]=pCakeArray[i];
        }
        m_nMaxSwap=UpperBound(m_nCakeCnt);
        m_SwapArray=new int[m_nMaxSwap+1];
        assert(m_SwapArray!=NULL);
        m_ReverseCakeArray=new int[m_nCakeCnt];
    }
    //寻找当前翻转的上界
    int UpperBound(int nCakeCnt){

    }
    //当前翻转的下界
    int LowBound(int nCakeCnt){

    }
    //排序的主函数
    void Search(int step){

    }
    //是否有序
    bool IsSorted(int* pCakeArray,int nCakeCnt){

    }
    //翻转烙饼信息
    void Revert(int nBegin,int nEnd){

    }
private:
    int* m_CakeArray;
    int m_nCakeCnt;
    int m_nMaxSwap;

    int* m_SwapArray;

    int* m_ReverseCakeArray;
    int* m_ReverseCakeArraySwap;
    int m_nsearch;
};